Technological advances have led to the conception of a variety of complex devices and systems. When a system fails, a technician or user typically fixes the system by identifying and replacing (or fixing) the failed component. To ease this process, a variety of model-based diagnostic tools have been developed that assist a user in identifying the failed component.
A diagnosis problem arises when a system's actual behavior fails to match the expected behavior, thereby exhibiting symptoms (anomalies). System diagnosis is then the task of identifying faulty components that are responsible for anomalous behavior. To solve the diagnosis problem, one typically finds the minimal set of faulty components that explain the observed symptoms. The most disciplined technique to diagnosis is termed “model-based” because it employs knowledge of devices' operations and their connectivities in the form of models. The model-based approach reasons from first principles and affords far better diagnostic coverage of a system than traditional rule-based diagnosis methods, which are based on a collection of specific symptom-to-suspect rules.
The diagnosis process starts with identifying symptoms that represent inconsistencies (discrepancies) between the system's model (description) and the system's actual behavior. Each symptom identifies a set of conflicting components (i.e., conflict set) as initial candidates. A minimal diagnosis set is the smallest set of components that intersects all conflict sets. The underlying general approach in different model-based diagnosis approaches can be described as a two-step “divide-and-conquer” technique wherein finding the minimal diagnosis set is accomplished in two steps: 1) Generating conflict sets from symptoms; and 2) Calculating minimal diagnosis set from the conflict sets. As shown in FIG. 1, the conflict generation corresponds to forming a collection of conflict sets 100, and calculating the minimal diagnosis 102 corresponds to the solution of the Hitting Set problem for this collection. The Hitting Set is the solution that would explain all of the symptoms.
However, there are major drawbacks in the current model-based diagnosis techniques in efficiently performing the above two steps that severely limit their practical application to many systems of interest. First, existing conflict-generating algorithms are all based on various versions of the constraint propagation method and truth maintenance systems. The problem with these methods is that not only do they need exponential time, but they also require exponential memory to be implemented. Therefore, these methods cannot handle realistic systems with a large number of components. Second, in order to find the minimal diagnosis set, current model-based diagnosis techniques rely on algorithms with exponential computational costs and thus, are highly impractical for application to many systems of interest.
Thus, a continuing need exists for a system that allows a user to efficiently identify a minimal diagnosis set for complex systems with a large number of components.